/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/number-of-subsquences-of-form-ai-bj-ck
   @Language: C++
   @Datetime: 19-04-19 16:01
   */

class Solution {
public:
	/**
	 * @param source: the input string
	 * @return: the number of subsequences 
	 */
	int countSubsequences(string &source) {
		// write your code here
		int n=source.length();
		vector<int> dpa(n+1,0), dpb(n+1,0), dpc(n+1,0);
		for(int i=0; i<n; ++i){
			if(source[i]!='a') dpa[i+1]=dpa[i];
			else dpa[i+1]=dpa[i]*2+1;
			if(source[i]!='b') dpb[i+1]=dpb[i];
			else dpb[i+1]=dpb[i]*2+dpa[i];
			if(source[i]!='c') dpc[i+1]=dpc[i];
			else dpc[i+1]=dpc[i]*2+dpb[i];
		}
		return dpc[n];
	}
};
